package DMSXL._2024.BinaryTrees;

import java.util.ArrayList;
import java.util.List;

public class pathSumIII {
    public static void main(String[] args) {
        Integer[] nums = {1,-2,-3,1,3,-2,null,-1};
        TreeNode root = CreateTree.createBinaryTree(nums,0);
        System.out.println(new pathSumIII().pathSum(root,-1));
    }
    List<TreeNode> list = new ArrayList<>();
    int max = 0;
    long path = 0;
    public int pathSum(TreeNode root, int targetSum) {
        preOrder(root);
        for (int i = 0; i < list.size(); i++) {
            path = 0;
            backTrack(list.get(i),targetSum);
        }
        return max;
    }
    public void backTrack(TreeNode root, int targetSum){
        path += root.val;
        if(targetSum == path){
            max++;
        }
        if(root.left != null){
            backTrack(root.left,targetSum);
            path -= root.left.val;
        }
        if(root.right != null){
            backTrack(root.right,targetSum);
            path -= root.right.val;
        }
    }
    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        list.add(root);
        preOrder(root.left);
        preOrder(root.right);
    }
}
